선형 방정식 시스템의 해법

(2.3)에서, 우리는 방정식 시스템의 일반적인 형태를 소개했다. 즉,

여기서 $a_{ij} \in \mathbb{R}$ 와 $b_i \in \mathbb{R}$ 은 알려진 상수들이고, $x_j$ 는 미지수들이다 ( $i=1, \dots, m, \ j=1, \dots, n$ ). 지금까지 우리는 선형 방정식을 $\boldsymbol{Ax} = \boldsymbol{b}$ 로 쓸 수 있도록 시스템을 공식화하는 간결한 방법으로 행렬을 사용할 수 있음을 보았다 (2.10 참조). 게다가, 우리는 행렬의 덧셈과 곱셈 같은 기본적인 행렬 연산들을 정의했다. 이어지는 내용에서, 우리는 선형 연립방정식을 푸는 데 초점을 맞추고 행렬의 역행렬을 구하는 알고리즘을 제공할 것이다.

2.3.1 특수 해와 일반 해

선형 연립방정식을 일반적으로 푸는 방법을 논의하기 전에, 예제를 하나 살펴보자. 다음의 방정식 시스템을 고려해 보자:

이 시스템은 두 개의 방정식과 네 개의 미지수를 가지고 있다. 따라서, 일반적으로 우리는 무수히 많은 해를 기대할 수 있다. 이 방정식 시스템은 특히 쉬운 형태를 띠고 있는데, 처음 두 열이 각각 1과 0으로 구성되어 있기 때문이다.
우리가 $\sum_{i=1}^4 x_i c_i = \boldsymbol{b}$ 가 되도록 하는 스칼라 $x_1, \dots, x_4$ 를 찾고 싶어 한다는 것을 기억하자(여기서 $c_i$ 는 행렬의 $i$ 번째 열이고 $\boldsymbol{b}$ 는 식 (2.38)의 우변이다). 식 (2.38)의 문제에 대한 해 중 하나는 첫 번째 열을 42번 가져오고 두 번째 열을 8번 가져옴으로써 즉시 찾을 수 있다. 즉:

따라서, $[42, 8, 0, 0]^\top$ 은 하나의 해가 된다. 이 해를 특수 해(particular solution) 또는 특별 해(special solution)라고 부른다.
하지만, 이것이 이 선형 연립방정식의 유일한 해는 아니다. 다른 모든 해를 포착하기 위해, 우리는 행렬의 열들을 사용하여 자명하지 않은 방식(non-trivial way)으로 0을 생성하는 창의적인 방법이 필요하다. 우리의 특수 해에 0을 더하는 것은 특수 해를 변화시키지 않기 때문이다. 이를 위해, 우리는 세 번째 열을 처음 두 열(매우 단순한 형태인)을 사용하여 표현해 본다:

따라서 $0 = 8c_1 + 2c_2 - 1c_3 + 0c_4$ 가 성립하며, $(x_1, x_2, x_3, x_4) = (8, 2, -1, 0)$ 을 얻는다. 사실, 이 해를 임의의 실수 $\lambda_1 \in \mathbb{R}$ 로 스케일링(배수)하더라도 여전히 0 벡터를 생성한다. 즉,

동일한 논리적 흐름을 따라, 우리는 식 (2.38) 행렬의 네 번째 열을 처음 두 열을 사용하여 표현하고, 다음과 같이 0의 또 다른 자명하지 않은(non-trivial) 버전을 생성할 수 있다.

여기서 $\lambda_2 \in \mathbb{R}$ 이다. 이 모든 것을 종합하면, 우리는 식 (2.38)의 방정식 시스템에 대한 모든 해를 얻게 되며, 이를 일반 해(general solution)라고 부른다. 집합으로 표현하면 다음과 같다:

참고. 우리가 따른 일반적인 접근 방식은 다음의 세 단계로 구성된다:

1. $Ax = b$ 에 대한 특수 해(particular solution)를 하나 찾는다.
2. $Ax = 0$ 에 대한 모든 해를 찾는다.
3. 1단계와 2단계의 해를 결합하여 일반 해를 만든다.

참고. 일반 해나 특수 해는 유일하지 않다. (예를 들어, 특수 해를 구할 때 $x_3, x_4$ 를 0으로 두지 않고 다른 숫자로 두면 또 다른 특수 해가 나온다).
$\quad$ 앞선 예제에서 선형 연립방정식을 쉽게 풀 수 있었던 이유는 식 (2.38)의 행렬이 특히 편리한 형태를 취하고 있었기 때문이다. 덕분에 우리는 직관적으로(by inspection) 특수 해와 일반 해를 찾아낼 수 있었다. 하지만, 일반적인 방정식 시스템은 이렇게 단순한 형태가 아니다. 다행히도, 임의의 선형 연립방정식 시스템을 이러한 특별히 단순한 형태로 변환하는 건설적이고 알고리즘적인 방법이 존재하는데, 그것이 바로 가우스 소거법(Gaussian elimination)이다. 가우스 소거법의 핵심은 선형 연립방정식 시스템의 기본 행 연산(elementary transformations)이며, 이는 방정식 시스템을 단순한 형태로 변환해 준다. 변환이 완료되면, 우리는 방금 (2.38)의 예제에서 논의했던 3단계를 단순해진 형태에 적용하여 해를 구할 수 있다.

2.3.2 기본 행 연산

선형 연립방정식을 푸는 열쇠는 기본 행 연산(elementary transformations)이다. 이것은 해 집합(solution set)을 그대로 유지하면서, 방정식 시스템을 더 단순한 형태로 변환한다:

• 두 방정식(방정식 시스템을 나타내는 행렬의 행들)의 교환 (Exchange)
• 방정식(행)에 0이 아닌 상수 $\lambda \in \mathbb{R} \setminus {0}$ 를 곱함 (Multiplication)
• 두 방정식(행)의 덧셈 (Addition)

$\quad$ 이어지는 내용에서, 우리는 선형 연립방정식의 특수 해와 일반 해를 얻는 건설적인 방법(constructive way)을 자세히 설명할 것이다.
참고 (피벗과 계단 구조). 한 행의 선도 계수(leading coefficient) (왼쪽에서부터 처음으로 나오는 0이 아닌 숫자)를 피벗(pivot)이라고 부른다. 피벗은 항상 바로 위 행의 피벗보다 엄격하게(strictly) 오른쪽에 위치한다. 따라서, 행사다리꼴(row-echelon form)로 정리된 모든 방정식 시스템은 항상 “계단(staircase)” 구조를 가진다.

참고 (기본 변수와 자유 변수). 행사다리꼴에서 피벗에 해당하는 변수들을 기본 변수(basic variables)라고 부르고, 나머지 변수들을 자유 변수(free variables)라고 부른다. 예를 들어, 식 (2.45)에서 $x_1, x_3, x_4$ 는 기본 변수이고, $x_2, x_5$ 는 자유 변수이다.
참고 (특수 해 구하기). 행사다리꼴은 우리가 특수 해를 결정해야 할 때 삶을 더 편하게 만들어 준다. 이를 위해, 우리는 방정식 시스템의 우변( $\boldsymbol{b}$ )을 오직 피벗 열(pivot columns)들만을 사용하여 표현한다. 즉 $\boldsymbol{b} = \sum_{i=1}^P \lambda_i \boldsymbol{p}_i$ 형태로 둔다. 여기서 $\boldsymbol{p}_i$ ( $i=1, \dots, P$ )는 피벗 열들이다. 계수 $\lambda_i$ 들은 가장 오른쪽 피벗 열부터 시작하여 왼쪽으로 작업을 진행하면 가장 쉽게 결정된다.
$\quad$ 앞선 예제에서, 우리는 다음을 만족하는 $\lambda_1, \lambda_2, \lambda_3$ 를 찾고자 할 것이다:

여기서부터, 우리는 비교적 직접적으로 $\lambda_3 = 1, \lambda_2 = -1, \lambda_1 = 2$ 임을 알 수 있다. 모든 것을 종합할 때, 우리는 계수를 암묵적으로 0으로 설정한 비-피벗 열(non-pivot columns)들을 잊어서는 안 된다. 따라서, 우리는 특수 해 $\boldsymbol{x} = [2, 0, -1, 1, 0]^\top$ 을 얻는다.
참고 (기약 행사다리꼴, Reduced Row Echelon Form). 어떤 방정식 시스템이 다음 조건들을 만족하면 기약 행사다리꼴(또는 행 간소화 사다리꼴, 행 정규형)이라고 한다:

• 행사다리꼴(row-echelon form)이다.
• 모든 피벗은 1이다.
• 피벗은 해당 열(column)에서 유일하게 0이 아닌 성분이다.

$\quad$ 기약 행사다리꼴(RREF)은 나중에 2.3.3절에서 중요한 역할을 하게 되는데, 왜냐하면 이것이 선형 연립방정식의 일반 해를 아주 간단하고 직접적인(straightforward) 방식으로 구할 수 있게 해주기 때문이다.
참고 (가우스 소거법, Gaussian Elimination). 가우스 소거법은 선형 연립방정식을 기약 행사다리꼴(reduced row-echelon form)로 변환하기 위해 기본 행 연산을 수행하는 알고리즘이다.

2.3.3 마이너스 1 트릭 (The Minus-1 Trick)

다음으로, 우리는 동차 선형 연립방정식 $\boldsymbol{Ax} = \boldsymbol{0}$ ( $A \in \mathbb{R}^{k \times n}, \boldsymbol{x} \in \mathbb{R}^n$ )의 해 $\boldsymbol{x}$ 를 읽어내는 실용적인 트릭을 소개한다.
시작하기 위해, 우리는 행렬 $\boldsymbol{A}$ 가 기약 행사다리꼴(RREF)이며 0으로만 구성된 행은 없다고 가정한다. 즉,

여기서 $*$ 는 임의의 실수를 나타내며, 각 행의 첫 번째 0이 아닌 성분은 반드시 1이어야 하고 해당 열의 다른 모든 성분은 0이어야 한다는 제약 조건이 있다. 피벗(굵은 글씨)이 포함된 열 $j_1, \dots, j_k$ 는 표준 단위 벡터 $\boldsymbol{e}_1, \dots, \boldsymbol{e}_k \in \mathbb{R}^k$ 이다.
우리는 이 행렬에 다음과 같은 형태의 $n-k$ 개의 행을 추가하여 $n \times n$ 행렬 $\tilde{\boldsymbol{A}}$ 로 확장한다:

이렇게 하면 확장된 행렬 $\tilde{\boldsymbol{A}}$ 의 대각선 성분은 1 또는 -1이 된다.
그러면, $\tilde{\boldsymbol{A}}$ 의 열들 중에서 피벗으로 -1을 포함하고 있는 열들이 바로 동차 연립방정식 $\boldsymbol{Ax} = \boldsymbol{0}$ 의 해가 된다. 더 정확하게 말하면, 이 열들은 $\boldsymbol{Ax} = \boldsymbol{0}$ 의 해 공간(solution space)의 기저(basis)를 형성하며, 우리는 나중에 이것을 커널(kernel) 또는 영공간(null space)이라고 부를 것이다 (2.7.3절 참조).

역행렬 계산
$A \in \mathbb{R}^{n \times n}$ 의 역행렬 $A^{-1}$ 를 계산하기 위해서, 우리는 $AX = I_n$ 을 만족하는 행렬 $X$ 를 찾아야 한다. 그러면 $X = A^{-1}$ 가 된다. 우리는 이것을 연립 일차방정식들의 집합 $AX = I_n$ 으로 쓸 수 있으며, 여기서 우리는 $X = [x_1 \vert \dots \vert x_n]$ 에 대해 푼다. 우리는 이 연립방정식 집합의 간결한 표현을 위해 첨가 행렬 표기법을 사용하며 다음과 같은 꼴을 얻는다.

이것이 의미하는 바는, 만약 우리가 첨가된 방정식 시스템을 기약 행사다리꼴(reduced row-echelon form)로 변환하면, 방정식 시스템의 우변에서 역행렬을 읽어낼 수 있다는 것이다. 따라서, 행렬의 역행렬을 결정하는 것은 연립 일차방정식을 푸는 것과 동치이다.

2.3.4 선형 연립방정식 해결을 위한 알고리즘

다음에서, 우리는 $Ax = b$ 형태의 선형 연립방정식을 푸는 접근법들을 간략히 논의한다. 우리는 해가 존재한다고 가정한다. 만약 해가 없다면, 우리는 근사 해(approximate solutions)에 의존해야 하는데, 이는 이 챕터에서는 다루지 않는다. 근사 문제를 해결하는 한 가지 방법은 선형 회귀(linear regression)의 접근법을 사용하는 것이며, 이는 9장에서 자세히 다룬다.
$\quad$ 특수한 경우, 우리는 $Ax = b$ 의 해가 $x = A^{-1}b$ 로 주어지는 역행렬 $A^{-1}$ 를 결정할 수 있을지도 모른다. 하지만, 이는 오직 $A$ 가 정사각 행렬이고 가역적(invertible)일 때만 가능한데, 실제로는 그렇지 않은 경우가 많다. 그렇지 않은 경우, 약한 가정(즉, $A$ 가 선형 독립인 열들을 가져야 함) 하에서 우리는 다음과 같은 변형을 사용할 수 있다:

그리고 무어-펜로즈 의사 역행렬(Moore-Penrose pseudo-inverse) $(A^\top A)^{-1}A^\top$ 를 사용하여 해 (2.59)를 결정할 수 있다. 이는 $Ax = b$ 를 푸는 최소 노름 최소 제곱 해(minimum norm least-squares solution)에 해당한다.
이 접근법의 단점은 행렬-행렬 곱( $A^\top A$ )과 $A^\top A$ 의 역행렬을 계산하는 데 많은 계산 비용이 든다는 것이다. 게다가, 수치적 정밀도(numerical precision)의 이유로 역행렬이나 의사 역행렬을 직접 계산하는 것은 일반적으로 권장되지 않는다. 따라서 다음 내용에서는 선형 연립방정식을 푸는 대안적인 접근법들을 간략히 논의한다.
$\to$ 현실 데이터 행렬은 대부분 정사각 행렬이 아니며, 정사각이라도 역행렬이 존재하지 않는 경우가 많다. 따라서 $A^T$ 를 양변에 곱해 의사 역행렬을 구하는 정규방정식을 사용한다. 이는 해가 없을 때, 에러를 최소화 하는 해를 찾아준다. 하지만 이는 연산량이 커질수록 컴퓨터의 부동소수점 오차도 커지기 때문에 수치적으로 불안정하다.
$\quad$ 가우스 소거법은 행렬식 계산(4.1절), 벡터 집합의 선형 독립성 확인(2.5절), 역행렬 계산(2.2.2절), 행렬의 랭크 계산(2.6.2절), 그리고 벡터 공간의 기저 결정(2.6.1절) 등을 수행할 때 중요한 역할을 한다. 가우스 소거법은 수천 개의 변수를 가진 선형 연립방정식을 푸는 직관적이고 건설적인(constructive) 방법이다. 하지만, 수백만 개의 변수를 가진 시스템의 경우, 필요한 산술 연산의 횟수가 연립방정식 개수의 세 제곱에 비례(scales cubically)하여 증가하므로 실용적이지 않다(impractical).
$\quad$ 실제로는, 많은 수의 선형 방정식을 포함하는 시스템은 간접적으로(indirectly) 풀리는데, 여기에는 Richardson 방법, Jacobi 방법, Gauß-Seidel 방법, 연속 과완화(successive over-relaxation) 방법과 같은 정상 반복법(stationary iterative methods)이나, 켤레 기울기(conjugate gradients), 일반화된 최소 잔여(generalized minimal residual), 이중 켤레 기울기(biconjugate gradients)와 같은 Krylov 부분공간 방법(Krylov subspace methods)이 사용된다. 더 자세한 내용은 Stoer and Burlirsch (2002), Strang (2003), Liesen and Mehrmann (2015)의 책들을 참고하기 바란다.
$\quad$ $x_*$ 를 $Ax = b$ 의 해라고 하자. 이러한 반복법들의 핵심 아이디어는 다음과 같은 형태의 반복(iteration)을 설정하는 것이다:

여기서 적절한 행렬 $C$ 와 벡터 $d$ 를 선택하여, 매 반복마다 잔차 오차(residual error) $\vert \vert x^{(k+1)} - x_*\vert \vert$ 를 줄여나가며 $x_*$ 에 수렴하게 만든다. 우리는 3.1절에서 벡터 간의 유사도(similarities)를 계산할 수 있게 해주는 노름(norm, $\Vert \cdot \Vert$ )을 소개할 것이다.